package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.ArrayList;
import java.util.Arrays;

/*
LeetCode60 
n个数的全排列，在所有组合找出字典序的第k个排列

 */
public class f全排列by对结果集字典序排列 {
	int count = 0;
	public static void main(String[] args) {
		String string = "CBA";
		
		f全排列by对结果集字典序排列 test = new f全排列by对结果集字典序排列();
		ArrayList<String> res1 = test.useGetPermutationByLexicographicalOrder(string);
		System.out.println(res1);
		
		test.useGetPermutationByLexicographicalOrderAndFindK(string, 3);
		
	}
	
	/**
	 * 字典序排序下的全排列
	 * 前置方法
	 * 会求出全部组合
	 * @param prefix
	 * @return
	 */
	public ArrayList<String> useGetPermutationByLexicographicalOrder(String string) {
		ArrayList<String> res = new ArrayList<String>();
		char[] arr = string.toCharArray();
		Arrays.sort(arr);
		getPermutationByLexicographicalOrder("", arr, res);
		return res;
	}
	
	/**
	 * 字典序排序下的全排列
	 * 核心语句
	 * @param prefix
	 * @param arr
	 * @param res
	 */
	public void getPermutationByLexicographicalOrder(String prefix, char[] arr, ArrayList<String> res) {//prefix前缀；
		if (prefix.length() == arr.length) {//递归出口
			res.add(prefix);
		}
		for (int i = 0; i < arr.length; i++) {//每次都从头扫描，只要该字符可用，我们就附加到前缀后面，前缀变长了
			char current = arr[i];
			if (count(prefix, current) < count(arr, current)) {//为什么要加上这个判断？因为考虑到arr中可能会有重复的字符
				getPermutationByLexicographicalOrder(prefix + current, arr, res);//这个字符可用意思是：在prefix中出现次数 < 在数组arr中的出现次数；prefix + current 的操作是“使前缀变长”
			}
		}
	}
	
	/**
	 * 找第K个字典序排序后的组合
	 * 前置方法
	 * @param string
	 * @param k
	 */
	public void useGetPermutationByLexicographicalOrderAndFindK(String string, int k) {
		char[] arr = string.toCharArray();
		Arrays.sort(arr);
		getPermutationByLexicographicalOrderAndFindK("", arr, k);
	}
	
	/**
	 * 递归形式
	 * 不必求出全部组合
	 * 找第K个字典序排序后的组合
	 * 核心语句
	 * @param prefix
	 * @param arr
	 * @param count
	 * @param k
	 */
	public void getPermutationByLexicographicalOrderAndFindK(String prefix, char[] arr, int k) {//prefix前缀；
		if (prefix.length() == arr.length) {//递归出口
			count++;//记录有多少个“组合”已经生成
			if (count == k) {//如果生成的个数已经 == 第k个
				System.out.println("目标是：" + prefix);//输出这个组合
				System.exit(0);//程序中断，不必再进行“生成组合”了
			}
			return;
		}
		for (int i = 0; i < arr.length; i++) {//每次都从头扫描，只要该字符可用，我们就附加到前缀后面，前缀变长了
			char current = arr[i];
			if (count(prefix, current) < count(arr, current)) {//为什么要加上这个判断？因为考虑到arr中可能会有重复的字符
				getPermutationByLexicographicalOrderAndFindK(prefix + current, arr, k);//这个字符可用意思是：在prefix中出现次数 < 在数组arr中的出现次数；prefix + current 的操作是“使前缀变长”
			}
		}
	}
	
	public int count(char[] arr, char current) {
		int count = 0;
		for (char c : arr) {
			if (c == current) {
				count++;
			}
		}
		return count;
	}
	
	public int count(String s, char current) {
		int count = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == current) {
				count++;
			}
		}
		return count;
	}
}
